package data_structures_and_algorithms.tree.traverse.classic;

import common.TreeNode;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName PreTraverse
 * @Description: 前序遍历：
 * @Author: yongliang.ma
 * @Create_time:2022/10/16 15:53
 */
public class PreTraverse {

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);

        node2.right = node3;
        node3.right = node1;
//        List<Integer> integers1 = new PreTraverse().preTraverseCur(node1);
//        System.out.println(Arrays.toString(integers1.toArray()));
        List<Integer> integers = new PreTraverse().preTraverseLoop(node2);
        System.out.println(Arrays.toString(integers.toArray()));
    }


    List<Integer> list = new LinkedList<>();

    public List<Integer> preTraverseCur(TreeNode treeNode){
        dfs(treeNode);

        return list;
    }

    public void dfs(TreeNode treeNode){
        if (treeNode == null)
            return;
        // 根
        list.add(treeNode.val);

        // 左
        preTraverseCur(treeNode.left);

        // 右
        preTraverseCur(treeNode.right);
    }

    public List<Integer> preTraverseLoop(TreeNode treeNode){
        if (treeNode == null)
            return list;
        Deque<TreeNode> deque = new LinkedList<>();
        TreeNode node = treeNode;
        // 两个条件搭配：栈 和 node节点
        while (!deque.isEmpty() || node != null){
            // 处理node节点，
            while (node != null){
                list.add(node.val);// 遍历到即打印
                deque.push(node);// 根节点压栈，然后左子节点上位
                node = node.left;
            }
            // 弹出栈顶元素，开始遍历右子节点
            node = deque.pop();
            node = node.right;
        }
        return list;
    }

    // 非常容易理解
    public class ZuoGodVersion{
        /**
         * 三个步骤：为什么先处理右孩子，因为先序遍历左在前，而栈压入和弹出顺序相反
         * 1、弹出即打印
         *
         * 2、如果有右孩子，右孩子压栈
         *
         * 3、如果有左孩子，左孩子压栈
         */
        public List<Integer> preTraverseLoop(TreeNode treeNode){
            if (treeNode == null)
                return list;
            Deque<TreeNode> deque = new LinkedList<>();
            deque.push(treeNode);
            while (!deque.isEmpty()){
                TreeNode node = deque.pop();
                list.add(node.val);// 弹出即打印
                if (node.right != null){// 先处理右孩子
                    deque.push(node.right);
                }
                if (node.left != null){
                    deque.push(node.left);
                }
            }
            return list;
        }
    }




}
